package linkedlistdemo;

public class MySingleList {
    //内部类   节点
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    ListNode head;
    //创建单链表
    public void createList() {
        ListNode node1 = new ListNode(11);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(56);
        ListNode node4 = new ListNode(42);
        head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    //打印单链表
    public void show() {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val +" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //计算单链表的长度
    public int size() {
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    //查找是否包含key
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //头插法
    public void headAdd(int val) {
        ListNode headAdd = new ListNode(val);
        headAdd.next = head;
        head = headAdd;
    }
    //尾插法
    public void endAdd(int val) {
        ListNode endAdd = new ListNode(val);
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = endAdd;
    }
    //在index位置插入数据val
    public void addIndex(int index,int val) {
        if(index < 0 || index > size()-1) {
            throw new OutOfIndexException("index不合法");
        }
        else if(index == 0) {
            headAdd(val);
        }
        else if(index == size()-1) {
            endAdd(val);
        }
        else {
            ListNode cur = head;
            for (int i = 1; i < index; i++) {
                cur = cur.next;
            }
            ListNode addVal = new ListNode(val);
            addVal.next = cur.next;
            cur.next = addVal;
        }

    }
    //删除数据第一次出现的key
    public void remove(int key) {
        if(head == null) return;

        ListNode cur = head;
        while(cur != null) {
            //判断第一个节点的val值是否为key
            if(head.val == key) {
                head = head.next;
                return;
            }
            ListNode lastKeyNode = findLastKey(key);
            if(lastKeyNode == null) {
                return;//没有找到要删除 val值为key 的节点
            }
            lastKeyNode.next = lastKeyNode.next.next;
            return;
        }
    }
    //找到第一个值为key的节点  的前一个节点
    public ListNode findLastKey(int key) {
        ListNode cur = head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除 所有 值为key 的节点
    public void removeAll(int key) {
        if(head == null) return;
        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null) {
            if(cur.val == key) {
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }

    //清空所有的节点
    public void clear() {
        if(head == null) return;
        ListNode cur = head;
        while(cur.next != null) {
            ListNode tmp = cur.next;
            cur.next = null;
            cur = tmp;
        }
        head = null;
    }
}
